package com.beaven.java.sort;

/**
 * @author Beaven
 * @date 2018/7/7 18:31
 * <p>
 * 归并排序
 * <p>
 * 总体思想：把大的数组拆分成多个小的数组，
 * 然后小的数组进行排序，再对小的数组进行合并排序，最后就可以得到有序的大数组
 */
public class MergeSort {

    // 辅助数组
    private static int[] temp;

    public static void sort(int[] nums) {
        temp = new int[nums.length];
        sortNum(nums, 0, nums.length - 1);
    }

    private static void sortNum(int[] nums, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        // 对大数组进行不断拆分
        int mid = lo + (hi - lo) / 2;
        sortNum(nums, lo, mid);
        sortNum(nums, mid + 1, hi);
        // 对数组进行归并排序
        merge(nums, lo, mid, hi);
    }

    private static void merge(int[] nums, int lo, int mid, int hi) {
        // 两个指针，数组划分两部分，指向最小值和中间值
        int i = lo;
        int j = mid + 1;
        // 辅助数组元素添值
        System.arraycopy(nums, lo, temp, lo, hi + 1 - lo);
        // 遍历要排序的数组
        // 排序规则：
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                // 1. 左边元素全部取完，取右边元素
                nums[k] = temp[j++];
            } else if (j > hi) {
                // 2. 右边元素全部取完，取左边元素
                nums[k] = temp[i++];
            } else if (temp[i] > temp[j]) {
                // 3. 左边的元素大于右边的元素，取右边的元素
                nums[k] = temp[j++];
            } else {
                // 4. 左边的元素小于右边的元素，取左边的元素
                nums[k] = temp[i++];
            }
        }
    }
}
